#include <bits/stdc++.h>

using namespace std;

// 至少有K个重复字符的最长子串
// 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串
// 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
// 如果不存在这样的子字符串，则返回 0。
// 测试链接 : https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/

class Solution 
{
public:
    int longestSubstring(string s, int k) 
    {
        int n = s.size();
        if(n < k) return 0;
        int cnts[128]{}, ans = 0;
        // 每次要求子串必须含有require种字符，每种字符都必须>=k次，这样的最长子串是多长
        for(int require = 1; require <= 26; ++require)
        {
            memset(cnts, 0, sizeof cnts);
            // collect : 窗口中一共收集到的种类数
			// satisfy : 窗口中达标的种类数(次数>=k)
            for(int l = 0, r = 0, collect = 0, satisfy = 0; r < n; ++r)
            {
                if(cnts[s[r]]++ == 0) ++collect;
                if(cnts[s[r]] == k) ++satisfy;
                // l....r 种类超了！
				// l位置的字符，窗口中吐出来！
                while(collect > require)
                {
                    if(cnts[s[l]] == 1) --collect;
                    if(cnts[s[l]] == k) --satisfy;
                    --cnts[s[l++]];
                }
                // l.....r : 子串以r位置的字符结尾，且种类数不超的，最大长度！
                if(satisfy == require) ans = max(ans, r - l + 1);
            }
        }
        return ans;
    }
};